package com.binaryTree;

public class CountCompleteTreeNodes0301_222 {
//    public int countNodes(TreeNode root) {
//        if(root == null) return 0;
//        return countNodes(root.left) + countNodes(root.right) + 1;
//    }

    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDeep = 0, rigthDeep = 0;
        while (left != null){
            left = left.left;
            leftDeep++;
        }
        while (right != null){
            right = right.right;
            rigthDeep++;
        }
        if(leftDeep == rigthDeep) return (2 << leftDeep) - 1;
        return countNodes(root.left) + countNodes(root.right) + 1;
    }

}
